package top.fengleifeng.question;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-10-16 10:21
 **/
public class Num45跳跃游戏II {
    //贪心算法
    class Solution {
        public int jump(int[] nums) {
            int length = nums.length;
            int end = 0;
            int maxPosition = 0;
            int steps = 0;
            for (int i = 0; i < length - 1; i++) {
                maxPosition = Math.max(maxPosition, i + nums[i]);
                if (i == end) {
                    end = maxPosition;
                    steps++;
                }
            }
            return steps;
        }
    }


//    class Solution {
//        public int jump(int[] nums) {
//            int length = nums.length;
//            if (length <= 1) {
//                return 0;
//            }
//            int step = 0;
//            int now = 0;
//            while (now < length) {
//                int nowMaxStep = now;
//                int max = now;
//                for (int i = 0; i < nums[now]; i++) {
//                    if (now + i + 1 < length) {
//                        max = Math.max(max, nums[now + i + 1]);
//                        if (nums[now + i + 1] == max) {
//                            nowMaxStep = now + i + 1;
//                        }
//                    } else {
//                        return ++step;
//                    }
//                }
//                now = nowMaxStep;
//                step++;
//            }
//            return step;
//        }
//    }
//        public int jump(int[] nums) {
//            int length = nums.length;
//            int[] step = new int[length];
//            //初始化数据
//            for (int i = 0; i < length; i++) {
//                step[i] = -1;
//            }
//            step[0] = 0;
//            for (int i = 0; i < length; i++) {
//                if (step[i] >= 0) {
//                    for (int j = 0; j < nums[i]; j++) {
//                        if (i + j + 1 >= length) {
//
//                        } else {
//                            if(step[i+j+1]==length-1){
//                                return step[i]+1;
//                            }else if (step[i + j + 1] < 0) {
//                                step[i + j + 1] = step[i] + 1;
//                            } else {
//                                step[i + j + 1] = Math.min(step[i] + 1, step[i + j + 1]);
//                            }
//                        }
//                    }
//                }
//            }
//            return step[length - 1];
//        }
//    }

    public static void main(String[] args) {
//        int[] ints = {2, 3, 1, 1, 4};
//        int[] ints = {0};
        int[] ints = {2, 1};
        int jump = new Num45跳跃游戏II().new Solution().jump(ints);
        System.out.println(jump);
    }
}
